#include "MiniState.h"
#include "Logger.h"
#include <iomanip>
#include <set>
#include <algorithm>

using namespace std;

map<size_t ,int> MiniState::miniStateEvalCache;

//Create a ministate just made up of the rectangle area indicated by topLeft to bottomRight in world coordinates
MiniState::MiniState(State* state,const Location& topLeft,const Location& bottomRight,const vector<Location>& antsThatMatter){
    int d1 = abs(topLeft.row-bottomRight.row);
    int d2 = abs(topLeft.col-bottomRight.col);
    rows = min(d1,abs(state->rows-d1));
    cols = min(d2,abs(state->cols-d2));
    tLeft = topLeft;
    bRight = bottomRight;
    antsInBattle = antsThatMatter;
    //    rows = abs(bottomRight.row - topLeft.row+1);
    //cols = abs(bottomRight.col - topLeft.col+1);
    //cerr<< "rows:" << rows << ",cols:" << cols << endl;
    Logger::theLogger() << "d1:" << d1<<",rows:" << rows << "d2:"<<d2<< ",cols:" << cols<<endl;

    grid = vector<vector<Square> >(rows, vector<Square>(cols,Square()));
    mainState= state;
    int i = topLeft.row;
    while(mainState->mapX(i)!=mainState->mapX(bottomRight.row)) {
        int j = topLeft.col;
        while(mainState->mapY(j)!=mainState->mapY(bottomRight.col)) {
            Location tLoc(mainState->mapX(i),mainState->mapY(j));
            //Logger::theLogger() << "tLoc:" << tLoc << endl;
            int miniStateRow= i-topLeft.row;//mapX(mainState->mapX(i));//i-topLeft.row;
            int miniStateCol = j-topLeft.col;//mapY(mainState->mapY(j));//j-topLeft.col;
            //            Logger::theLogger() << "i:"<< i << ",miniStateRow:" << miniStateRow << "j:" << j <<",miniStateCol:"<<miniStateCol << endl;

            grid[miniStateRow][miniStateCol] = mainState->grid[tLoc.row][tLoc.col];
            if ((grid[miniStateRow][miniStateCol].ant>=0))  {
                 if (find(antsThatMatter.begin(),antsThatMatter.end(),
                          Location(mainState->mapX(miniStateRow+tLeft.row),
                                   mainState->mapY(miniStateCol+tLeft.col)))!=antsThatMatter.end()) {
                     antsInBattle.push_back(Location(miniStateRow,miniStateCol));
                 }
                 Logger::theLogger() << "pushing Ant" << Location(miniStateRow,miniStateCol) << endl;
                 playerAntList[grid[miniStateRow][miniStateCol].ant].push_back(Location(miniStateRow,miniStateCol));
            }
            j++;
        }
        i++;
    }
    Logger::theLogger()<<*this;
}

Location MiniState::getLocation(const Location &loc, int direction) const
{
    return Location( (loc.row + DIRECTIONS[direction][0] + rows) % rows,
                     (loc.col + DIRECTIONS[direction][1] + cols) % cols );
};

int MiniState::mockMakeMove(const Location& loc,int direction) {
    int ant = grid[loc.row][loc.col].ant;
    Location nLoc = getLocation(loc, direction);
    int saveAnt = grid[nLoc.row][nLoc.col].ant;
    grid[nLoc.row][nLoc.col].ant = grid[loc.row][loc.col].ant;
    grid[loc.row][loc.col].ant = -1;
    vector<Location>::iterator it;
    if ((it = find(playerAntList[ant].begin(),playerAntList[ant].end(),loc))!=playerAntList[ant].end()) {
        playerAntList[ant].erase(it);
        playerAntList[ant].push_back(nLoc);
    }
    return saveAnt;
}

void MiniState::unmakeMockMove(const Location& loc,int direction,int savedAnt) {
    Location nLoc = getLocation(loc, direction);
    grid[loc.row][loc.col].ant = grid[nLoc.row][nLoc.col].ant;
    grid[nLoc.row][nLoc.col].ant = savedAnt;
    vector<Location>::iterator it;
    if ((it = find(playerAntList[savedAnt].begin(),playerAntList[savedAnt].end(),nLoc))!=playerAntList[savedAnt].end()) {
        playerAntList[savedAnt].erase(it);
        playerAntList[savedAnt].push_back(loc);
    }
}

/** resolve any battles and remove the dead ants from the state
 *  should normally be invoked after making moves in the min step of a minmax to 
 *  simulate the game as a turn by turn game
 */
int MiniState::resolveBattles() {
    Logger::theLogger() << "Entered resolveBattles() " << endl;
    set<Location> antsToKill;
    for(map<int,vector<Location> >::iterator it = playerAntList.begin();it!=playerAntList.end();it++) {
        int player_id = it->first;
        vector<Location> playerAnts = it->second;
        for(vector<Location>::iterator antIt = playerAnts.begin();antIt!=playerAnts.end();antIt++) {
            vector<Location> enemyAntList;
            findThisAntsEnemiesInRadius(*antIt,mainState->attackradius,enemyAntList,player_id);
            Logger::theLogger() <<"first enemyAntQuery" << endl;
            for(vector<Location>::iterator enemyIt = enemyAntList.begin();enemyIt!=enemyAntList.end();enemyIt++) {
                vector<Location> thisEnemyAntsEnemyList;
                findThisAntsEnemiesInRadius(*enemyIt,mainState->attackradius,thisEnemyAntsEnemyList,grid[enemyIt->row][enemyIt->col].ant);
                Logger::theLogger() <<"second enemyAntQuery" << endl;

                if (thisEnemyAntsEnemyList.size() < enemyAntList.size()) {
                    antsToKill.insert(*antIt);
                }
                else if(thisEnemyAntsEnemyList.size() ==enemyAntList.size()) {
                    antsToKill.insert(*antIt);
                    antsToKill.insert(*enemyIt);
                }
                else {
                    antsToKill.insert(*enemyIt);
                }
            }
        }
    }
    Logger::theLogger() << "Erasing all killed ants" << endl;
    for(set<Location>::iterator it=antsToKill.begin();it!=antsToKill.end();it++) {
        Logger::theLogger() << "Erasing ant at:" << *it << ":"<<grid[it->row][it->col].ant << endl;
        playerScores[grid[it->row][it->col].ant]-=2;
        vector<Location>::iterator it2;
        if ((it2=find(playerAntList[grid[it->row][it->col].ant].begin(),
                      playerAntList[grid[it->row][it->col].ant].end(),
                      *it))!=playerAntList[grid[it->row][it->col].ant].end()) {
            
            playerAntList[grid[it->row][it->col].ant].erase(it2);
            grid[it->row][it->col].ant = -1;

        }
    }
    Logger::theLogger() << "Checking hill razing ants" << endl;
    for(map<int,vector<Location> >::iterator it = playerAntList.begin();it!=playerAntList.end();it++) {
        int player_id = it->first;
        Logger::theLogger() << "player_id is :" << player_id << endl;
        vector<Location> playerAnts(it->second);
        for(vector<Location>::iterator antIt = playerAnts.begin();antIt!=playerAnts.end();antIt++) {
            if (player_id==0) {
                if (grid[antIt->row][antIt->col].isHill &&
                    (grid[antIt->row][antIt->col].hillPlayer!=player_id)) {
                    playerScores[player_id]+=100;
                }
            }
            else {
                if (grid[antIt->row][antIt->col].isHill &&
                    (grid[antIt->row][antIt->col].hillPlayer==0)) {
                    playerScores[0]-=100;
                    
                }
                else if (grid[antIt->row][antIt->col].isHill &&
                    (grid[antIt->row][antIt->col].hillPlayer!=player_id)) {
                    playerScores[player_id]-=20;
                }
            }
        }
    }
    Logger::theLogger() << "Exited resolveBattles()" << endl;
}

bool MiniState::checkCache(int& score) {
    size_t hashVal = std::tr1::hash<MiniState>()(*this);
    if (miniStateEvalCache.find(hashVal)!=miniStateEvalCache.end()) {
        score= miniStateEvalCache[hashVal];
        return true;
    }
    return false;
}

int MiniState::eval(int player_id) {
    Logger::theLogger() << "Entered eval for player_id:" << player_id<< endl;
    Logger::theLogger() << *this;
    int score=0;
    // if (checkCache(score)) {
    //     Logger::theLogger() << "returning cached eval:" << score << endl;
    //     return score;
    // }
    if (playerScores.find(player_id)!=playerScores.end()) {
        score = playerScores[player_id];
    }
    if (playerAntList.find(player_id)==playerAntList.end()) {
        Logger::theLogger() << "Player has no ants left" << endl;
        Logger::theLogger() <<"Exiting eval" << endl;
        return score;
    }
    vector<Location> playerAnts = playerAntList[player_id];    
    for(vector<Location>::iterator it = playerAnts.begin();it!=playerAnts.end();
        it++) {
        vector<Location> enemyAntList;
        findThisAntsEnemiesInRadius(*it,mainState->attackradius,enemyAntList,player_id);
        for (vector<Location>::iterator it2 = enemyAntList.begin();it2!=enemyAntList.end();it2++) {
            vector<Location> thisEnemyAntsEnemyList;
            findThisAntsEnemiesInRadius(*it2,mainState->attackradius,thisEnemyAntsEnemyList,grid[it2->row][it2->col].ant);
            if (thisEnemyAntsEnemyList.size() < enemyAntList.size()) {
                Logger::theLogger() << "An enemy has less enemy ants this one " << endl;
                score-=25;
            } 
            else if (thisEnemyAntsEnemyList.size() > enemyAntList.size()) {
                Logger::theLogger() << "An enemy ant has more enemies than this one" << endl;
                score+=5;
                if (enemyHillInView(*it,mainState->viewradius)) {
                    Logger::theLogger() << "Enemy hill is in view " << endl;
                    score+=50;
                }
                if (grid[it->row][it->col].isHill && grid[it->row][it->col].hillPlayer) {
                    Logger::theLogger() << "an ant is on top of a enemy hill" << endl;
                    score+=100;
                }
            }
            else if (thisEnemyAntsEnemyList.size() == enemyAntList.size()) {
                //give a bonus if either an enemy hill is in view
                //or if my ants outnumber the enemies in the area
                Logger::theLogger() << "Enemy has same number of ants as us" << endl;
                if (enemyHillInView(*it,mainState->viewradius/2)) {
                    Logger::theLogger() <<"Enemy hill in view " << endl;
                    score+=15;
                }
                if (myHillInView(*it,mainState->viewradius)) {
                    Logger::theLogger() << "My hill in view so be a bit more aggressive" << endl;
                    score+=15;
                }
                int myAnts = playerAntList[player_id].size();
                int enemyAnts = 0;
                for(map<int,std::vector<Location> >::iterator antListIter = playerAntList.begin();antListIter!=playerAntList.end();antListIter++) {
                    if (antListIter->first==0 ) 
                        continue;
                    enemyAnts+=antListIter->second.size();
                }
                if (myAnts>enemyAnts*3) {
                    score+=5;
                }
                else if (myAnts<enemyAnts){
                    score-=5;
                }
                Location antLocOnMainMap = Location(mainState->mapX(it->row+tLeft.row),mainState->mapY(it->row+tLeft.col));
                for(vector<Location>::iterator hillIt=mainState->myHills.begin();hillIt!=mainState->myHills.end();hillIt++) {
                    int dist = mainState->distance(antLocOnMainMap,*hillIt); 
                    score -= dist/mainState->viewradius;
                }
                //give one bonus for tigher configurations
                for(int i=0;i<TDIRECTIONS;i++) {
                    Location nLoc = getLocation(*it,i);
                    if (grid[nLoc.row][nLoc.col].ant==0) 
                        score+=1;
                }
            }
        }
    }


    Logger::theLogger() << "Exited eval with score:" << score << " for player: " << player_id << endl;
    miniStateEvalCache[std::tr1::hash<MiniState>()(*this)] = score;
    return score;
}

bool MiniState::myHillInView(const Location& loc,const double& radius) const {
    int offset = round(radius);

    Location start,end;    
    start.row = loc.row-offset;
    start.col = loc.col-offset;
    end.row = loc.row+offset;
    end.col = loc.col+offset;

    int i = start.row;

    while (i<=end.row) {
	int j = start.col;
	while(j<=end.col) {
	    //translate i/j from world coordinates to map coordinates
	    //and lookup the grid, 
	    //TODO: if the radius is greater than rows/2 and cols/2
	    //it might be more efficient to search the whole grid rather than
	    //use this loop. it will also cause ants to be added twice right now.
	    Location tLoc(mapX(i),mapY(j));
	    if (((grid[tLoc.row][tLoc.col].isHill) && (grid[tLoc.row][tLoc.col].hillPlayer==0)) && 
		(distance(tLoc,loc) <=radius)) {
		return true;
	    }
	    j++;
	}
	i++;
    }
    return false;
}

bool MiniState::enemyHillInView(const Location& loc,const double& radius) const {
    int offset = round(radius);

    Location start,end;    
    start.row = loc.row-offset;
    start.col = loc.col-offset;
    end.row = loc.row+offset;
    end.col = loc.col+offset;

    int i = start.row;

    while (i<=end.row) {
	int j = start.col;
	while(j<=end.col) {
	    //translate i/j from world coordinates to map coordinates
	    //and lookup the grid, 
	    //TODO: if the radius is greater than rows/2 and cols/2
	    //it might be more efficient to search the whole grid rather than
	    //use this loop. it will also cause ants to be added twice right now.
	    Location tLoc(mapX(i),mapY(j));
	    if (((grid[tLoc.row][tLoc.col].isHill) && (grid[tLoc.row][tLoc.col].hillPlayer!=0)) && 
		(distance(tLoc,loc) <=radius)) {
		return true;
	    }
	    j++;
	}
	i++;
    }
    return false;
}

bool MiniState::findPath(const Location& startLoc,const Location& endLoc,
                         stack<int>& path, int& numNodesExplored,
                         int player_id) const {
    priority_queue<PathNode> openQueue;
    openQueue.push(PathNode(distance(startLoc,endLoc),startLoc));
    
    map<Location,bool> closedSet;
    vector< vector<int> > visited(rows,vector<int>(cols,0));
    //all nodes
    int depth = 1;
    numNodesExplored = 0;
    bool found=false;
    visited[startLoc.row][startLoc.col] = depth;
    while (!openQueue.empty()) {
	numNodesExplored++;
	PathNode curNode = openQueue.top();
	openQueue.pop();
	Location curLoc = curNode.loc;
	closedSet[curLoc] =true;
	if (curLoc.row == endLoc.row && curLoc.col == endLoc.col) {
	    found = true;
	    break;
	}
	else {
	    //Search didn't terminate so explore adjoining nodes
	    depth+=1;//increase depth of search tree by 1
	    for (int d=0;d<TDIRECTIONS;d++) {
		Location nLoc = getLocation(curLoc,d);
		if (closedSet.find(nLoc)!=closedSet.end())  {
		    continue;
		}
		if (nLoc==endLoc)  {
		    visited[nLoc.row][nLoc.col]  = visited[curLoc.row][curLoc.col]+1;
		    found=true;
		    break;
		}
		if (!grid[nLoc.row][nLoc.col].isWater && //don't route over water
		    (grid[nLoc.row][nLoc.col].lastSeen!=0) &&
		    (grid[nLoc.row][nLoc.col].ant!=player_id))// &&
		    //!grid[nLoc.row][nLoc.col].isHill)
		    {
			//if the node has not yet been visited
			//and is not water and has been seen before
			//then explore this node
		    
			if (visited[nLoc.row][nLoc.col]==0) {
			    visited[nLoc.row][nLoc.col] = visited[curLoc.row][curLoc.col]+1;
			    openQueue.push(PathNode(visited[nLoc.row][nLoc.col]+distance(nLoc,endLoc),nLoc));
			}
			else if (visited[nLoc.row][nLoc.col]>(visited[curLoc.row][curLoc.col]+1)) {
			    visited[nLoc.row][nLoc.col] = visited[curLoc.row][curLoc.col]+1;
			}
		    }
	    }
	    if (found) 
		break;
	}
    }
    //if we found an ant extract the Path
    //and return the ant location and the path from the ant to the location
    if (found) {
	extractPath(endLoc,startLoc,visited,path);
        //	if (path.empty()) {
#ifdef DEBUG
	    for (int i=0;i<rows;i++)  {
		for (int j=0;j<cols;j++) {
		    if (visited[i][j]==1) {
			Logger::theLogger() << setw(3) << "*";
		    }
		    else if ((i==endLoc.row) && (j==endLoc.col)) {
			Logger::theLogger() << setw(3)<< "#";
		    }
		    else if (visited[i][j]!=0) {    
			Logger::theLogger() << setw(3) << visited[i][j];
		    }
		    else {
			Logger::theLogger() << setw(3) << "0" ;
		    }
		}
		Logger::theLogger() <<endl;
	    }
            //    return false;
            //}
#endif
	return true;
    }
    else {
	Logger::theLogger() << "Path finding failed for "  << startLoc << " to " << endLoc << endl;
#ifdef DEBUG
	for (int i=0;i<rows;i++)  {
	    for (int j=0;j<cols;j++) {
		if (visited[i][j]==1) {
		    Logger::theLogger() << setw(3) << "*";
		}
		else if ((i==endLoc.row) && (j==endLoc.col)) {
		    Logger::theLogger() << setw(3)<< "#";
		}
		else if (visited[i][j]!=0) {    
		    Logger::theLogger() << setw(3) << visited[i][j];
		}
		else {
		    Logger::theLogger() << setw(3) << "0" ;
		}
	    }
	    Logger::theLogger() <<endl;
	}
#endif
	return false;
    }
}

//multidimensional array of visited nodes
void MiniState::extractPath(const Location& startLoc,const Location& endLoc,const vector< vector<int> >& visited,stack<int>& path) const{
    Logger::theLogger() << "Extracting path from startLoc: " << startLoc << " to endLoc:" << endLoc << endl;
    
    Location curLoc  = startLoc;

    while (visited[curLoc.row][curLoc.col]!=1){
	double min_dist = LARGEVAL+0.1;
	int direction;
	Location nextLoc;
	int min_visited=visited[curLoc.row][curLoc.col];
	bool first =true;
	for(int d=0;d<TDIRECTIONS;d++) {
	    Location nLoc = getLocation(curLoc,d);
	    if ((visited[nLoc.row][nLoc.col]!=0) &&
		(visited[nLoc.row][nLoc.col] < visited[curLoc.row][curLoc.col])
		) 
	    {
                if (first) {
		    first = false;
		    min_visited = visited[nLoc.row][nLoc.col];
		    min_dist = distance(nLoc,startLoc);
		    direction = d;
		    nextLoc = nLoc;
		}
		else if (distance(nLoc,startLoc) < min_dist) {
		    min_visited = visited[nLoc.row][nLoc.col];
		    min_dist = distance(nLoc,startLoc);
		    direction = d;
		    nextLoc = nLoc;
		}	
                //Logger::theLogger() << " min_dist:" << min_dist << ",direction:"<<CDIRECTIONS[direction] << endl;
	    }
	}
	//we need to index with a trick to reverse directions
	path.push((direction+2)%4);
	curLoc = nextLoc;
    }
}

//returns the euclidean distance between two locations with the edges wrapped
double MiniState::distance(const Location &loc1, const Location &loc2) const
{
    int d1 = abs(loc1.row-loc2.row),
        d2 = abs(loc1.col-loc2.col),
        dr = min(d1, rows-d1),
        dc = min(d2, cols-d2);
    return sqrt(dr*dr + dc*dc);
};

void MiniState::findThisAntsEnemiesInRadius(const Location& loc,const double& radius,vector<Location>& antList,int player_id) const {
    int offset = round(radius)+1;

    Location start,end;    
    start.row = loc.row-offset;
    start.col = loc.col-offset;
    end.row = loc.row+offset;
    end.col = loc.col+offset;

    int i = start.row;
    Logger::theLogger() << "searching start:" << start << ",end:" << end << " for enemies" << endl;
    while (i<=end.row) {
	int j = start.col;
	while(j<=end.col) {
	    //translate i/j from world coordinates to map coordinates
	    //and lookup the grid, 
	    //TODO: if the radius is greater than rows/2 and cols/2
	    //it might be more efficient to search the whole grid rather than
	    //use this loop. it will also cause ants to be added twice right now.
	    Location tLoc(mapX(i),mapY(j));
            //            Logger::theLogger() << tLoc <<":" << grid[tLoc.row][tLoc.col].ant << endl;

	    if ((grid[tLoc.row][tLoc.col].ant>=0) && 
		(grid[tLoc.row][tLoc.col].ant!=player_id) &&
		(distance(tLoc,loc) <=radius)
		) {
		antList.push_back(tLoc);
	    }
	    j++;
	}
	i++;
    }
}

pair<Location,int> MiniState::translateMoveToMainMap(pair<Location,int> move) {
    return pair<Location,int>(Location(mainState->mapX(move.first.row+tLeft.row),mainState->mapY(move.first.col+tLeft.col)),move.second);
}

std::ostream& operator<<(std::ostream &os,const MiniState& state) {
#ifdef DEBUG
    for(int row=0; row<state.rows; row++)
    {
        os << setw(3) << row << " ";
        for(int col=0; col<state.cols; col++)
        {
            if(state.grid[row][col].isWater)
                os << '%';
            else if(state.grid[row][col].isFood)
                os << '*';
            else if(state.grid[row][col].isHill)
                os << (char)('A' + state.grid[row][col].hillPlayer);
            else if(state.grid[row][col].ant >= 0)
                os << (char)('a' + state.grid[row][col].ant);
            else if(state.grid[row][col].lastSeen == 0)
                os << '?';
            else
                os << '.';
        }
        os << endl;
    }
#endif
    return os;
}

bool MiniState::findClosestAnt(const Location& loc,Location& antLoc,stack<int>& path) {
    queue< Location > openQueue;
    openQueue.push(loc);

    //We use visited to track the path and extract it once we find the target
    vector < vector<int> >  visited(rows,vector<int>(cols,0));
    //we search around the location till we hit an ant or we exhaust 
    //all nodes
    int depth = 1;
    int numNodesExplored = 0;
    Location finalLoc;
    bool found=false;
    visited[loc.row][loc.col] = depth;

    while (!openQueue.empty()) {
	numNodesExplored++;
	Location curLoc = openQueue.front();
	openQueue.pop();
	if (grid[curLoc.row][curLoc.col].ant>=0)
	{
	    finalLoc = curLoc;
	    found = true;
	    break;
	}
	else {
	    //Search didn't terminate so explore adjoining nodes
	    depth+=1;//increase depth of search tree by 1
	    for (int d=0;d<TDIRECTIONS;d++) {
		Location nLoc = getLocation(curLoc,d);
		if ((visited[nLoc.row][nLoc.col]==0) &&// explore only unvisited nodes 
		    !grid[nLoc.row][nLoc.col].isWater && //don't route over water
		    !grid[nLoc.row][nLoc.col].isHill && //don't route over hills
		    (grid[nLoc.row][nLoc.col].lastSeen!=0)  
		    ) {
		    //if the node has not yet been visited
		    //and is not water and has been seen before
		    //then explore this node
		    visited[nLoc.row][nLoc.col] = visited[curLoc.row][curLoc.col]+1;
		    openQueue.push(nLoc);
		}
	    }
	}
    }
    //if we found an ant extract the Path
    //and return the ant location and the path from the ant to the location
    if (found) {
	extractPath(finalLoc,loc,visited,path);
	antLoc = finalLoc;
	return true;
    }
    else 
	return false;
}
